/**
 * 
 * @author Pietro & Rohmin Mirza
 *
 */
public class RSHeap
{
	private int[] heap;
	private int maxsize;
	private int size;
	
	/**
	 * 
	 * @param arr
	 */
	public RSHeap( int max )
	{
		maxsize = max;
		heap = new int[maxsize];
		size = 0 ;
		heap[0] = Integer.MIN_VALUE;
	}

	/**
	 * 
	 */
	public void buildHeap()
	{
		for( int i=0; i< heap.length;i++ )
		{
			int posL = getLChildOf(i);
			int posR = getRChildOf(i);
			
			if( (posL>0)&&(heap[i]>heap[posL]) )
			{
				percoladeUp( posL );
			}

			if( (posR>0)&&(heap[i]>heap[posR]) )
			{
				percoladeUp( posR );
			}
		}
	}
	
	/**
	 * 
	 * @param posX
	 */
	public void percoladeUp( int posX )
	{
		int parentPos = getParentPosOf(posX);
		while( ( parentPos != -1)&&( heap[parentPos]>heap[posX]) )
		{
			//int[] copy = myArray.clone();
			int tmp = heap[parentPos];
			heap[parentPos] = heap[posX];
			heap[posX] = tmp;
			posX = parentPos;
			parentPos = getParentPosOf(posX);
		}
	}
	
	/**
	 * 
	 * @param pos1
	 * @param pos2
	 */
	private void swap(int pos1, int pos2) 
	{
		int tmp;

		tmp = heap[pos1];
		heap[pos1] = heap[pos2];
		heap[pos2] = tmp;
	}
	
	/**
	 * 
	 * @param elem
	 */
	public void insert(int elem) 
	{
		size++;
		heap[size] = elem;
		int current = size;

		while (heap[current] < heap[getParentPosOf(current)])
		{
			swap(current, getParentPosOf(current));
			current = getParentPosOf(current);
		}	
	}
	
	/**
	 * 
	 * @param newLast
	 */
	public void setLast(int newLast)
	{
		heap[size] = newLast;
	}
	
	/**
	 * 
	 * @return
	 */
	public int getSmallest()
	{
		return heap[0];
	}
	
	/**
	 * 
	 * @param index
	 * @return
	 */
	public int getElement(int index)
	{
		return heap[index];
	}
	
	/**
	 * 
	 * @return
	 */
	public int size()
	{
		return size;
	}
	public void setElement(int index, int element)
	{
		heap[index] = element;
	}
	
	/**
	 * 
	 * @param newMin
	 */
	public void setMin(int newMin){
		heap[0]= newMin;
	}

	/**
	 * 
	 * @return
	 */
	public int[] getHeapArray(){
		return heap;
	}
	
	/**
	 * 
	 * @return
	 */
	public int getLast()
	{
		return heap[size];
	}
	
	/**
	 * 
	 */
	public void moveLastToDeadspace()
	{
		size--;
	}
	
	/**
	 * 
	 * @param posN
	 * @return
	 */
	public int getParentPosOf( int posN )
	{
		if( posN > 0 )
		{
			return ((posN-1)/2);
		}
		else
		{
			return -1;
		}
	}
	
	/**
	 * 
	 * @param posN
	 * @return
	 */
	public int getLChildOf( int posN )
	{
		if( (2*posN+1) < heap.length)
		{
			return 2*posN+1;
		}
		else
		{
			return -1;
		}
	}
	
	/**
	 * 
	 * @param posN
	 * @return
	 */
	public int getRChildOf( int posN )
	{
		if( (2*posN+2) < heap.length )
		{
			return (2*posN+2);
		}
		else
		{
			return -1;
		}
	}
	
	
	/**
	 * 
	 */
	public void print()
	{
		int i;
		for (i=1; i<=size;i++)
		{
			System.out.print(heap[i] + " ");
		}
		System.out.println();
	}

	/**
	 * 
	 * @return
	 */
	public int removemin()
	{
		swap(1,size);
		size--;
		if (size != 0)
		{
			percoladeUp(1);
		}
		return heap[size+1];
	}

}
